/*
 * GeneralGraph.java
 *
 * Created on 2007年10月10日, 上午11:50
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
package com.exclamation.util.graph;

import java.util.Iterator;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 *
 * @author littlerock
 */
public class GeneralGraphImp extends AbstractGraphImp {

    /**
     * Creates a new instance of GeneralGraph
     */
    public GeneralGraphImp() {
    }

    public GeneralGraphImp(boolean directed) {
        super(directed);
    }

    public GeneralGraphImp(boolean directed, int vSize, int eSize) {
        super(directed, vSize, eSize);
    }

    protected Vertex creaeVertex(int id) {
        return new GeneralVertex(id);
    }

    protected Edge createEdge(int id, int from, int to) {
        Vertex tail = this.getVertex(from);
        Vertex head = this.getVertex(to);
        Edge e = new GeneralEdge(id, tail, head);
        ((GeneralVertex) tail).oes.add(e);
        ((GeneralVertex) head).ies.add(e);
        if (!this.isDirected()) {
            ((GeneralVertex) tail).ies.add(e);
            ((GeneralVertex) head).oes.add(e);
        }
        return e;
    }

    protected void removeEdgeRelation(int e) {
        GeneralEdge edge = (GeneralEdge) getEdge(e);
        GeneralVertex tail = (GeneralVertex) edge.getTail();
        GeneralVertex head = (GeneralVertex) edge.getHead();
        tail.oes.remove(edge);
        head.ies.remove(edge);
        if (edge.isDirected() == false) {
            tail.ies.remove(edge);
            head.oes.remove(edge);
        }
        edge.setTail(null);
        edge.setHead(null);
    }

    protected void removeVertexRelation(int v) {
    }

    protected GraphImp createNewGraphImp(boolean directed) {
        return new GeneralGraphImp(directed);
    }

    class GeneralVertex extends AbstractVertex {

        SortedSet<Edge> ies = new TreeSet<Edge>(EdgeComparator.getEdgeComparator());
        SortedSet<Edge> oes = new TreeSet<Edge>(EdgeComparator.getEdgeComparator());

        GeneralVertex(int id) {
            super(id);
        }

        GeneralVertex(int id, Object value) {
            super(id, value);
        }

        public Edge[] getOutEdges() {
            Edge[] edges = new Edge[oes.size()];
            return this.oes.toArray(edges);
        }

        public Edge[] getInEdges() {
            Edge[] edges = new Edge[ies.size()];
            return this.ies.toArray(edges);
        }

        public Edge[] getEdges() {
            if (!this.getGraph().isDirected()) {
                Edge[] edges = new Edge[this.ies.size()];
                return ies.toArray(edges);
            }
            TreeSet<Edge> inter = new TreeSet<Edge>(EdgeComparator.getEdgeComparator());
            Iterator<Edge> i1 = this.ies.iterator();
            Iterator<Edge> i2 = this.oes.iterator();
            Edge e1 = null;
            Edge e2 = null;
            if (i1.hasNext()) {
                e1 = i1.next();
            }
            if (i2.hasNext()) {
                e2 = i2.next();
            }
            while (e1 != null & e2 != null) {
                if (e1.getId() == e2.getId()) {
                    inter.add(e1);
                    if (i1.hasNext()) {
                        e1 = i1.next();
                    } else {
                        e1 = null;
                    }
                    if (i2.hasNext()) {
                        e2 = i2.next();
                    } else {
                        e2 = null;
                    }
                } else if (e1.getId() > e2.getId()) {
                    if (i2.hasNext()) {
                        e2 = i2.next();
                    } else {
                        e2 = null;
                    }
                } else {
                    if (i1.hasNext()) {
                        e1 = i1.next();
                    } else {
                        e1 = null;
                    }
                }
            }
            Set<Edge> cloned = new TreeSet<Edge>(EdgeComparator.getEdgeComparator());
            cloned.addAll(this.ies);
            cloned.removeAll(inter);
            cloned.addAll(this.oes);
            Edge[] edges = new Edge[cloned.size()];
            return cloned.toArray(edges);
        }

        public Graph getGraph() {
            return GeneralGraphImp.this;
        }
    }

    class GeneralEdge extends AbstractEdge {

        Vertex tail;
        Vertex head;

        public GeneralEdge(int id, Vertex tail, Vertex head) {
            this(id, tail, head, null);
        }

        public GeneralEdge(int id, Vertex tail, Vertex head, Object value) {
            super(id, value);
            this.head = head;
            this.tail = tail;
        }

        public Vertex getTail() {
            return this.tail;
        }

        public Vertex getHead() {
            return this.head;
        }

        public Graph getGraph() {
            return GeneralGraphImp.this;
        }

        void setTail(Vertex v) {
            this.tail = v;
        }

        void setHead(Vertex v) {
            this.head = v;
        }
    }
}
